1. Field of Invention
This invention relates generally to semiconductor memories and specifically to content addressable memories.
2. Description of Related Art
A content addressable memory (CAM) device is a storage device having an array of memory cells that can be instructed to compare the specific pattern of a comparand data with data words stored in corresponding rows of the array. The entire CAM array, or segments thereof, are searched in parallel for a match with the comparand data. If a match exists, the CAM device indicates the match condition by asserting a match flag, and may indicate the existence of multiple matches by asserting a multiple match flag. The CAM device typically includes a priority encoder that provides the highest priority matching address (e.g., the lowest CAM index) to a status register. The highest priority matching address, the contents of the matched location, and other status information (e.g., skip bit, empty bit, full flag, as well as match and multiple match flags) may be output from the CAM device to an output bus.
CAM devices may be depth cascaded together to form a larger CAM device or system. For example, two 1024 (1 k)xc3x9764 CAM devices may be depth cascaded together to form a 2 kxc3x9764 CAM device. Depth cascading may be implemented in a first configuration by forming a chain of CAM devices each having a match flag input pin and a match flag output pin, and for each CAM device, connecting its match flag output pin to the match flag input pin of the next CAM device. The first CAM device in the chain, which may represent the highest priority addresses (e.g., lowest CAM index), has its match flag input pin connected to a predetermined logic level to indicate that there is no previous CAM device. The match output pin of the last CAM device in the cascaded chain provides a system match flag indicative of match conditions in the CAM devices.
In response to a compare instruction, each CAM device simultaneously compares a comparand word with data stored in its respective CAM array. If a CAM device has a match, it forwards its asserted match flag to the next CAM device (e.g., the next highest priority CAM device). The CAM device may then output its match address to a common output bus, and the lower priority CAM device will be disabled from outputting data to the common output bus. If, however, the CAM device does not have a match, it will not assert its match flag output, and the lower priority CAM device may provide its match address to the common output data bus (if it has a match).
If there are many CAM devices depth cascaded together, then the lowest priority CAM device in the cascade will only be able to output its data to the common output bus if no other CAM devices in the cascade have a match. In this first prior art configuration, the lowest priority CAM device must wait until the match flag signals from the previous CAM devices have rippled through each device in the cascaded chain. This may result in an undesirably long time to generate the system match flag, and for the last CAM device to output data to the common output data bus. Since match flag information must ripple through each device in this cascaded system, the time required to generate the system match flag, as well as the time required for the last CAM device to resolve its match priority, is linearly related to the number of cascaded devices, and may be expressed as t=tmf+(nxe2x88x921)xcex1, where tmf is the time delay associated with generating a match flag for a CAM device, n is the number of cascaded devices, and a is the delay associated with combining match information from a previous CAM device with the internal match flag for the CAM device. Where many devices are cascaded in this manner, the time t=tmf+(nxe2x88x921)xcex1 may become large and no longer fit within a period of the system clock. As a result, the clock period may need to be increased to accommodate the delay in generating the system match flag and resolving priority, which in turn may adversely affect the operating frequency of the cascaded system.
One solution to increase speed is to provide the match flag of each CAM device to all lower priority devices in the cascaded chain. This second prior art configuration eliminates the gate delay associated with waiting for the higher priority match flags to ripple through the cascaded chain, but undesirably increases the number of match flag input pins required for each CAM device linearly with an increase in the number of cascaded devices. Since each CAM device would receive the match flags of all previous CAM devices in the chain, the last CAM device of such a system having n devices requires nxe2x88x921 match flag input pins. Thus, although able to generate the system match flag much faster than the first prior art configuration, the second prior art configuration undesirably requires an additional match flag input pin for each additional cascaded device, and therefore consumes more silicon area than the first prior art configuration. In addition, connecting a match flag output pin to a match flag input pin of each lower-priority device may undesirably increase loading of the match flag output pin, which in turn may degrade performance.
Therefore, there is a need for a cascade configuration that achieves a balance between the number of match flag input pins required per cascaded device and the time required to generate a system flag for the cascaded devices.
A method and apparatus are disclosed for hierarchically cascading a number of memory devices in a manner that achieves a balance between the number of match flag input pins and the time required to generate the system match flag. In some embodiments, the number of match pins required for each cascaded device and the time required to generate a system match flag are each logarithmically related to the number of cascaded devices. In one embodiment, an m-level hierarchy of groups are defined for up to n memory devices, where m=log2n and m is an integer greater than 2. The first hierarchy may include n/2 groups of 2 memory devices, the second hierarchy may include n/4 groups of 4 memory devices, and so on, where the last hierarchy may include one group of n devices. Each group in a given hierarchical level includes a pair of groups from the preceding hierarchical level. At each hierarchical level, the match flag generated by the first of the group""s pair may be provided to the highest priority and the lowest priority device (e.g., the first and the last device) in the second of the group""s pair. In some embodiments, the system match flag may be generated in a time t=tmf+mxcex1, where tmf is the time required to generate a match flag, and xcex1is the gate delay associated with logically combining an internal match flag with match flags received from other devices.
In other embodiments, at each hierarchical level, the match flag(s) generated by devices in the first of the pair defined in the previous hierarchical level are selectively provided to all devices in the second of the pair defined in the previous hierarchical level. In such embodiments, the selective interconnections made between groups defined in different hierarchical levels may allow for generating the system match flag and resolving priority amongst the CAM devices in a time t=tmf+mxcex1.
In some embodiments, each CAM device includes cascade logic that allows input match information received from other (e.g., higher-priority) devices to be selectively combined with the device""s internal match flag to generate output match information and/or to resolve priority. The output match information may be selectively combined with other match information in another (e.g., lower priority) device. The cascade logic includes a memory element for storing one or more select values that determine whether one or more corresponding input match flags received from other devices will participate with the device""s internal match flag in generating the output match information. In one embodiment, the memory element is a look-up table that stores select values for all devices cascaded in the system and provides the select values to corresponding devices according to a unique device identification (ID) assigned to each device.